package DataStrucures;

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[]arr={4,6,8,5,9};
//        BubblingSorting(arr);
//        SelectSort(arr);
//        InsertSort(arr);
//        HillSort(arr);
//        QuickSort(arr,0,arr.length-1);
//        int[] temp=new int[arr.length];
//        MergeSort(arr,0,arr.length-1,temp);

//        CardinalitySort(arr);
        heapsort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void BubblingSorting(int[] arr){//冒泡排序
        int len=arr.length;
        int temp=0;
        int count=0;//优化算法
        for (int i = 0; i < len-1; i++) {
            for (int j = 0; j < len-i-1; j++) {
                if(arr[i]>arr[i+1]){
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                    count++;
                }
                if(count==0){
                    break;
                }
                count=0;
            }
        }
    }public static void SelectSort(int[] arr){//选择排序
        int len=arr.length;
        int temp=0;
        int x=0;
        for (int i = 0; i < len-1; i++) {
            int min=arr[i];
            for (int j = i; j < len; j++) {
                if(min>arr[j]){
                    min=arr[j];
                    x=j;
                }
            }
            if(min!=arr[i]){
                temp=arr[i];
                arr[i]=min;
                arr[x]=temp;
            }
        }
    }
    public static void InsertSort(int[] arr){//插入排序
        int len=arr.length;
        int temp;
        for (int i = 1; i <len ; i++) {
            if(arr[i]>arr[i-1]){
                continue;
            }

            for (int j =0; j <i ; j++) {

                if(arr[j]>arr[i]){//发现插入位置进行插入
                    temp=arr[i];
                    for (int k = i; k >j ; k--) {
                        arr[k]=arr[k-1];
                    }
                    arr[j]=temp;
                    break;
                }
            }

        }
    }
    public static void HillSort(int[] arr){//希尔排序交换法
         int len=arr.length;
         int x=len/2;
         int temp;
         while (true){
             for (int i = 0; i < len-x; i++) {//分组进行插入排序（有点类似选择排序）
                 for (int j = i; j <len ; j+=x) {
                     if(arr[i]>arr[j]){
                         temp=arr[i];
                         arr[i]=arr[j];
                         arr[j]=temp;
                     }
                 }
             }
             if(x==1){
                 break;
             }
             x=x/2;
         }

    }
//    public static void ShiftSorting(int[] arr){//希尔排序移位法对插入排序进行优化的结果（分组在进行插入排序）
//        int len=arr.length;
//        int x=len/2;
//        int temp;
//        while (true){
//            for (int i = 0; i < len-x; i++) {//分组进行插入排序（有点类似选择排序）
//                for (int j = i; j <len ; j+=x) {
//
//                }
//            }
//            if(x==1){
//                break;
//            }
//            x=x/2;
//        }
//
//    }
    public static void QuickSort(int[] arr,int left,int right){//快速排序法
        int l=left;
        int r=right;
        int pivot=arr[(l+r)/2];
        int temp;
        while (l<r){
            while (arr[l]<pivot){
                l+=1;
            }
            while (arr[r]>pivot){
                r-=1;
            }
            if(l>=r){
                break;
            }
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
            if(arr[l]==pivot){
                r-=1;
            }if(arr[r]==pivot){
                l+=1;
            }
        }
        if(l==r){
            r-=1;
            l+=1;
        }
        if(left<r){
            QuickSort(arr,left,r);
        }
        if(right>l){
            QuickSort(arr,l,right);
        }


    }
    public static void MergeSort(int[] arr,int left,int right,int[] temp){//归并排序的分
        if(left<right){
            int mid=(left+right)/2;
            MergeSort(arr,left,mid,temp);
            MergeSort(arr,mid+1,right,temp);
            Merge(arr,left,right,mid,temp);
        }
    }

    public static void Merge(int[] arr,int left,int right,int mid,int[] temp){//归并排序的和
        int i=left;
        int j=mid+1;
        int t=0;
        while (i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t]=arr[j];
                t++;
                j++;
            }
        }while (i<=mid){
            temp[t]=arr[i];
            t++;
            i++;
        }while (j<=right){
            temp[t]=arr[j];
            t++;
            j++;
        }
        t=0;
        int tempLeft=left;
        while (tempLeft<=right){
            arr[tempLeft]=temp[t];
            t++;
            tempLeft++;
        }
    }
    public static void CardinalitySort(int[] arr){//基数排序
        int len=arr.length;

        int count=0;
        while (true){

            int[]num=new int[10];//记录桶中的实际数量
            int[][]bucket=new int[10][len];
            for (int i = 0; i < len; i++) {//按位数的值进行分类
                int k=Number(arr[i],count);
                bucket[k][num[k]]=arr[i];
                num[k]++;
            }
            int k=0;
            for (int i = 0; i < 10; i++) {//将桶中的数放回数组中
                for (int j = 0; j < num[i]; j++) {

                    arr[k]=bucket[i][j];
                    k++;
                }
            }

            if(num[0]==len){
                break;
            }
            count++;
        }
    }
    public static int Number(int a,int i){//获取第I位数
        int x=(int)Math.pow(10,i);
        a=a/x;
        return a%10;
    }
    public static void heapsort(int[] arr){//堆排序
        for (int i = (arr.length/2)-1; i >=0; i--) {//形成大顶堆（增序排列）

            adjustHeap(arr,i, arr.length);
        }
        int temp;//将数组转换成从小到大(思路是将最大点固定在尾部，再将剩下的节点中找到最大的值重复操作)
        for (int i = arr.length-1; i >0 ; i--) {
            temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,i);
        }
    }
    public static void adjustHeap(int[] arr,int i,int length){
        int temp=arr[i];
        for (int j = i*2+1; j < length; j=j*2+1) {//比较俩个子节点中的数是否大于父节点如果大于则交换
            if(arr[j]<arr[j+1]&&j+1<length){
                j++;
            }if(arr[j]>temp){
                arr[i]=arr[j];
                i=j;
            }else{
                break;
            }
        }
        arr[i]=temp;
    }
}
